package top.humbleyuan.dichotomy;

/**
 * @Author HumbleYuan
 * @Date 2020/5/18 20:56
 * @Des
 */
public class LeetCode_74 {
    public static void main(String[] args) {
        /**
         * 先二分找到所在行，再二分进行行内搜索
         */

//        int[][] matrix = {
//                {1,   3,  5,  7},
//                {10, 11, 16, 20},
//                {23, 30, 34, 50}
//        };

        int[][] matrix = {{-9,-9,-9,-8,-8,-7,-6,-4,-4,-3},
                {0,1,2,2,4,5,5,5,7,9},
                {12,12,14,14,15,17,19,19,19,21},
                {22,23,23,25,25,26,26,28,28,29},
                {31,31,31,33,34,36,37,38,38,39},
                {40,42,43,44,46,46,46,47,49,50},
                {52,54,55,57,59,60,60,62,64,66},
                {68,68,70,71,71,72,74,76,78,80},
                {82,83,85,85,85,87,88,88,89,89},
                {90,90,90,91,93,94,94,95,95,97},
                {98,98,99,99,101,103,105,106,108,109},
                {112,112,112,113,113,113,114,116,118,118},
                {119,121,122,124,125,125,125,126,127,128},
                {131,133,134,134,134,135,135,137,137,139},{141,143,145,147,148,150,150,150,150,152},{153,153,154,155,157,157,157,159,161,162},{164,166,167,167,167,169,170,170,171,173},{176,176,178,179,181,182,183,183,184,186}};

        int target = 135;

        int pre = 0, back = matrix.length - 1;
        int maxCol = matrix[0].length - 1;

        // 和一般二分不同，先逼近到两个相邻行
        while(pre < back - 1) {
            int mid = (back- pre) / 2 + pre;
            if(matrix[mid][maxCol] == target) {
                System.out.println(true);
                return;
            }

            if(matrix[mid][maxCol] > target) {
                back = mid;
            } else {
                pre = mid;
            }
        }

        // 两行判断
        if(matrix[pre][maxCol] == target || matrix[back][maxCol] == target) {
            System.out.println(true);
            return;
        }

        int row;
        if(target < matrix[pre][maxCol]) {
            row = pre;
        } else {
            row = back;
        }

        pre = 0;
        back = matrix[row].length - 1;
        while(pre <= back) {
            int mid = (back- pre) / 2 + pre;
            if(matrix[row][mid] == target) {
                System.out.println(true);
                return;
            }

            if(matrix[row][mid] > target) {
                back = mid - 1;
            } else {
                pre = mid + 1;
            }
        }

        System.out.println(false);
    }
}
